package leetcode;
import java.util.*;
/**
 * 216.组合总和Ⅲ
 * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 * 说明：
 * 所有数字都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1:
 * 输⼊: k = 3, n = 7
 * 输出: [[1,2,4]]
 * 示例 2:
 * 输⼊: k = 3, n = 9
 * 输出: [[1,2,6], [1,3,5], [2,3,4]]
 */
public class Num_216 {
    List<Integer> inner = new ArrayList<>();
    List<List<Integer>> outter = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(n, k, 1);
        return outter;
    }

    private void dfs(int n, int k, int startIndex) {
        //边界条件
        if(inner.size() == k && sum(inner) == n){
            outter.add(new ArrayList<>(inner));
            return;
        }
        for(int i = startIndex; i <= 9; i++){
            inner.add(i);
            dfs(n, k, i + 1);
            inner.remove(inner.size() - 1);
        }
    }
    //计算数组中的元素总和
    private int sum(List<Integer> inner) {
        int count = 0;
        for (int i = 0; i < inner.size(); i++) {
            count += inner.get(i);
        }
        return count;
    }
}
